package com.zang.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ZVerify
 * @since 2022/10/30 16:18
 * @see <a href="https://leetcode.cn/problems/minimum-depth-of-binary-tree/">...</a>
 **/
public class 二叉树的最小深度 {

    public int minDepth(TreeNode root) {
        // 如果为null则返回0
        if (root==null) return 0;
        // 只有根节点则返回0
        if (root.left==null&&root.right==null) return 1;
        int sum = 0;
        Deque<TreeNode> list = new LinkedList<>();
        list.add(root);
        // 层序遍历,在过程中碰到哪层含有左右子节点都为null的节点则为最小深度
        while (!list.isEmpty()){
            sum++;
            int size = list.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = list.pollFirst();
                if (treeNode.left!=null) list.add(treeNode.left);
                if (treeNode.right!=null) list.add(treeNode.right);
                if (treeNode.left==null&&treeNode.right==null) return sum;
            }
        }
        return sum;
    }
}
